/**
 * Copyright (c) [2025] [何屹林]
 *
 * 保留所有权利。
 *
 * 文件名称：LR0.cpp
 * 模块功能说明：
 * 该模块实现LR0相关分析，定义生成LR0内容的各种函数，并构建LR0状态表和转移表，在生成LR0的过程中判断是否为SLR1文法。
 *
 * 华南师范大学-计算机学院-网络工程-1班
 * 作者：何屹林-20222132023
 * 完成日期：2025年7月24日
 */

#include "LR0.h"

LR0_state LR0_state::closure(LR0_state I, QHash<QString, QSet<QStringList>> grammars, QVector<QString> nonFinalizers, QHash<QString, QSet<QString>> first_set)
//伊普西隆闭包，从一个部分状态I生成LR0的完整的状态
{
    LR0_state J=I;
    while(1)
    {
        for(auto it:J.st)
        {
            if(it.pos<it.rule.size()&&nonFinalizers.contains(it.rule[it.pos]))
            {
                QString pre_word=it.rule[it.pos];
                for(auto g:grammars[pre_word])
                {
                    Item newItem;
                    newItem.name =pre_word;
                    newItem.rule = g;
                    newItem.pos = 0;
                    if (!J.st.contains(newItem)) J.st.insert(newItem);
                }
            }
        }
        if (I == J) break;
        I = J;
    }
    return J;
}

LR0_state LR0_state::change(LR0_state I, QString X, QHash<QString, QSet<QStringList>> grammars, QVector<QString> nonFinalizers, QHash<QString, QSet<QString>> first_set)
{
    LR0_state I_new;
    for (auto item: I.st) {
        if (item.pos >= item.rule.size() || item.rule[item.pos] != X) continue;         //根本不能移进

        Item newItem;
        newItem.name = item.name;
        newItem.rule = item.rule;
        newItem.pos = item.pos + 1;//移进一个位置

        // 判断I_new中是否已经出现了newItem
        if (!I_new.st.contains(newItem)) I_new.st.insert(newItem);//无则添加
    }
    if (I_new.st.empty()) return I_new;
    else return closure(I_new, grammars, nonFinalizers, first_set);
}

void LR0::buildLR0(LR0_state first_state, QHash<QString, QSet<QStringList>> grammars, QVector<QString> nonFinalizers,
                   QHash<QString, QSet<QString>> first_set, QHash<QString, QSet<QString>> follow_set)
{
    int first_state_id = state_hash[first_state];

    // 找到可能的转移方法
    QStringList changeMethods;
    for (auto first_item: first_state.st) {
        if (first_item.pos < first_item.rule.size())//首先pos不能超出rule的长度
        {
            changeMethods.append(first_item.rule[first_item.pos]);
        }
    }

    // 深搜每个转移
    for (QString changeMethod: changeMethods)
    {
        LR0_state sub_state = LR0_state::change(first_state, changeMethod, grammars, nonFinalizers, first_set);
        if (sub_state.st.empty()) continue;
        if (state_hash.contains(sub_state))//若状态存在，则指向其，若不存在，则创建新的状态并指向其
        {
            // 该状态已经存在
            int sonStateId = state_hash[sub_state];
            change_hash[first_state_id].insert(changeMethod, sonStateId);
        } else {
            // 该状态不存在
            state_hash[sub_state] = size++;
            change_hash[first_state_id].insert(changeMethod, state_hash[sub_state]);
            buildLR0(sub_state, grammars, nonFinalizers, first_set, follow_set);
        }
    }
}

bool LR0::is_SLR1(QHash<QString, QSet<QString>> follow_set) {
    for (auto st : state_hash.keys()) {
        QVector<QString> reduceSymbols; // 存储所有归约项的左部非终结符

        // 收集所有可归约的非终结符
        for (auto it : st.st) {
            if (it.pos == it.rule.size()) {
                reduceSymbols.append(it.name);
            }
        }

        // 归约-归约冲突：检查每对非终结符的Follow集是否相交
        for (int i = 0; i < reduceSymbols.size(); ++i) {
            for (int j = i + 1; j < reduceSymbols.size(); ++j) {
                QString A = reduceSymbols[i];
                QString B = reduceSymbols[j];
                if (!follow_set[A].intersect(follow_set[B]).isEmpty()) {
                    return false; // Follow集有交集，冲突
                }
            }
        }

        // 移进-归约冲突：检查移进符号是否在任何归约项的Follow集中
        for (auto it : st.st) {
            if (it.pos < it.rule.size()) {
                QString symbol = it.rule[it.pos];
                for (QString A : reduceSymbols) {
                    if (follow_set[A].contains(symbol)) {
                        return false; // 符号在Follow(A)中，冲突
                    }
                }
            }
        }
    }
    return true;
}


QString LR0::SLR1(QHash<QString, QSet<QString>> follow_set) {
    for (auto st : state_hash.keys()) {
        QVector<QString> reduceSymbols;

        // 收集归约项的非终结符
        for (auto it : st.st) {
            if (it.pos == it.rule.size()) {
                reduceSymbols.append(it.name);
            }
        }

        // 检测归约-归约冲突
        for (int i = 0; i < reduceSymbols.size(); ++i) {
            for (int j = i + 1; j < reduceSymbols.size(); ++j) {
                QString A = reduceSymbols[i];
                QString B = reduceSymbols[j];
                if (!follow_set[A].intersect(follow_set[B]).isEmpty()) {
                    return "存在归约-归约冲突！";
                }
            }
        }

        // 检测移进-归约冲突
        for (auto it : st.st) {
            if (it.pos < it.rule.size()) {
                QString symbol = it.rule[it.pos];
                for (QString A : reduceSymbols) {
                    if (follow_set[A].contains(symbol)) {
                        return "存在无法解决的移进-归约冲突！";
                    }
                }
            }
        }
    }
    return "";
}

size_t qHash(const LR0_state &key)
{
    return qHash(key.st);
}


